The Internet is a set of networks connected by routers. A router maintains a routing table that indicates for each possible destination network, the next hop to which a received data packet should be forwarded. The next hop may be another router or the final destination.
An Internet Protocol (xe2x80x9cIPxe2x80x9d) data packet received at a port in a router includes an IP destination address. The IP destination address is the final destination of the IP data packet. Currently there are two versions of IP, IP version 4 (xe2x80x9cIPv4xe2x80x9d) and IP version 6 (xe2x80x9cIPv6xe2x80x9d). IPv4 provides a 32-bit field in an IP header included in the data packeted for storing the IP destination address. The router forwards a received data packet connected to a next-loop router or the final destination if the destination is the local network, dependent on the IP destination address stored in the IP header.
A 32-bit IPv4 destination address provides 4 billion possible routes. An Internet router typically stores 50,000 of the 4 billion possible routes. However, the number of stored routes will increase with the growth of the Internet and the widespread use of IPv6.
Originally, the IP address space was divided into three classes of IP addresses; A, B and C. Each IP address space was divided into a network address and a host address. Class A allowed for 126 networks and 16 million hosts per network. Class B allowed for 16382 networks with 64,000 hosts per network and class C allowed for 2 million networks with 256 hosts per network. However, dividing the IP address space into different classes reduced the number of available IP addresses. Class C only allowed a maximum of 256 hosts per network which is too small for most organizations. Therefore, most organizations were assigned a Class B address, taking up 64,000 host addresses which could not be used by other organizations even if they were not used by the organization to which they were assigned. Hosts in an organization with a Class B IP address all store the same network address in the 16 Most Significant Bits (xe2x80x9cMBSsxe2x80x9d), for example, 128.32.xx.xx.
Classless InterDomain Routing (xe2x80x9cCIDRxe2x80x9d) was introduced to free up unused IP host addresses. The remaining unused networks are allocated to organization in variable sized blocks. An organization requiring 500 addresses gets 500 continuous addresses. For example, an organization can be assigned 500 available addresses starting at 128.32.xx. The number of routes stored by a router has increased since the introduction of Classless InterDomain Routing. Classless InterDomain Routing requires longest prefix matching to find the corresponding route instead of searching for a matching network address in order to find the corresponding next hop for the IP destination address. For example, a search can no longer stop after the 16 MSBs of a Class B IP address, for example, 128.xx.xx because 128.32.4.xx may be assigned to another organization requiring a different next hop.
One method for searching for a longest prefix match for a key is through the use of a binary tree search. A binary tree search matches a 32-bit input bit by bit down to 32 levels, requiring 32 searches to finding the entry matching the 32-bit key. Another method for searching for a match is through the use of a Patricia tree. A Patricia tree reduces the number of searches required if there are no entries down a leaf of the binary tree.
Yet another method for efficiently searching for a next hop associated with an IP destination address is described in PCT application Ser. No. PCT/SE98/00854 entitled xe2x80x9cMethod and System for Fast Routing Lookupsxe2x80x9d by Brodnick et al. filed on May 11, 1998. The method described by Brodnick reduces the number of next hops stored by not storing duplicate routes. By reducing the number of next hops, the memory requirement is reduced so that a route lookup table can be stored in fast cache memory.
Brodnick et al. divides the binary tree into 3-levels. Dividing the binary tree into 3-levels reduces the number of searches to three. The indexed entry in the first level indicates whether the search can end at the first level with the route taken from the entry, or the search must continue to a subsequent level using a further portion of the IP destination address.
FIG. 1A illustrates a prior art 64K (65536) bit map representing the first level of a binary tree. A 64K bit map 30 represents the leaves or nodes 44 of the binary tree at depth 16, with one bit per node 44. The bit map is divided into bit-masks of length 16. There are 212=4096 bit masks in the 64k bit map. One bit mask is shown in FIG. 1A. A bit in the bit map 30 is set to xe2x80x981xe2x80x99 if there is a subtree or a route index stored in an array of pointers corresponding to the node 44. A bit in the bit map 30 is set to xe2x80x980xe2x80x99 if the node shares a route entry with a previous node 44.
FIG. 1B illustrates prior art lookup table implemented in cache memory. The lookup table includes an array of code words 36, an array of base indices 34 and a map table 40. A 32-bit IP address 38 is also shown in FIG. 1B. A codeword 46 is stored in the array of code words 36 for each bit mask in the bit map 30 (FIG. 1A). The code word 46 includes a six-bit value 46a and a 10-bit offset 46b. A base index 42 is stored in the array of base indices 34 for every four code words 46 in the array of code words 36.
The array of code words 36, array of base indices 34 and map table 40 are used to select a pointer in an array of pointers (not shown). The pointer stores a route index or an index to perform a further search.
A group of pointers in the array of pointers is selected by selecting a code word 46 in the array of code words 36 and a base index 42 in the array of base indices 34. The code word 46 is selected using the first 12 bits 50 of the IP address 38. The base index 42 is selected using the first 10 bits 48 of the IP address 38. The correct pointer in the group of pointers is selected using the map table 32.
The 10-bit value 46b in the selected code word 36 is an index into the map table 32. The map table 32 maps bit numbers within a bit-mask to 4-bit offsets. The offset specifies the pointer within the selected group of pointers in the array of pointers. The 10-bit value 46b selects the row in the map table 32 and bits 19:16 of the IP address 52 selects the 4-bit offset 54.
Thus, a search for a pointer requires the following cache memory accesses: (1) read a 16 bit code word 46; (2) read a 16-bit base address 42; (3) read a 4 bit offset 54 from the map table 32; (4) read a pointer at a pointer index where the pointer index is the sum of the base address 42, the code word offset 46a and the 4-bit offset 54.
The same memory accesses are required for each level of the binary tree. Thus, a search of three levels requires 12 memory accesses.
A method for efficiently searching for a next hop associated with an IP destination address is described in PCT application Serial Number PCT/SE98/00854 entitled xe2x80x9cMethod and System for Fast Routing Lookupsxe2x80x9d by Brodnick et al. filed on May 11, 1998. Brodnick et al. describes a method for reducing the number of bytes required for a subtree which is sparse; that is a subtree for which there are less than 8 routes stored. 24 bytes of memory are allocated to store the 8 routes for the sparse subtree. The 24 bytes include an array of eight 8-bit route entries which store values corresponding to the search key and a respective 16-bit pointer for each route entry.
The values are stored in an array in memory in decreasing order. The array is searched to find the value less than or equal to the search key. Multiple accesses to the memory are required. At most seven memory accesses may be required to find the value corresponding to the search key.
A lookup table which allows multiple sparse subtree descriptors to be stored in a subtree entry in a memory is presented. The lookup table includes a plurality of subtree entries accessed by a subtree index. A dense subtree descriptor is stored in a first of the subtree entries. The dense subtree descriptor includes a value indication for each leaf of the dense subtree. A plurality of sparse subtree descriptors is stored in a second of the subtree entries. Each of the sparse subtree descriptors includes at least one node descriptor.
The node descriptor identifies a common value for a set of leaves of a sparse subtree. The memory stores both sparse subtree descriptors and dense subtree descriptors. A dense subtree descriptor is stored in a first subtree entry. The dense subtree descriptor includes a bit per leaf of a dense subtree. The dense subtree descriptor indicates values for the leaves of the dense subtree. A plurality of sparse subtree descriptors is stored in a second subtree entry. Each sparse subtree descriptor includes at least one node descriptor. The node descriptor identifies a common value for a set of leaves of a sparse subtree.
Mapper logic the value corresponding the leaf of the dense subtree dependent on the number of bits set to xe2x80x981xe2x80x99 in the dense subtree descriptor. The number of bits provided for storing sparse subtree descriptors in a subtree entry is equal to the number of bits in the dense subtree descriptor.
The node descriptor is encoded using run length encoding. The number of bits in the node descriptor is equal to the number of bits in the subtree leaf plus one. Values for multiple subtree leaves are encoded in the node descriptor dependent on the position of the first least significant bit set to xe2x80x981xe2x80x99. The number of bits in the node descriptor is 9 and the number of bits in the subtree leaf is 8.
A Content Addressable Memory searchable by the subtree leaf is provided. Conversion logic selects the node descriptor in the selected sparse subtree descriptor, converts the node descriptor to an 8-bit encoded value and stores the 8-bit encoded value in the Content Addressable Memory. The node descriptor is converted by setting least significant bits to the right of the first least significant bit set to xe2x80x981xe2x80x99 to xe2x80x9cdon""t carexe2x80x9d and removing the first least significant bit set to xe2x80x981xe2x80x99.